{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pairs With Sum LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pairSums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数对和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [5,6,5], target = 11\n",
    "<strong>输出: </strong>[[5,6]]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [5,6,5,6], target = 11\n",
    "<strong>输出: </strong>[[5,6],[5,6]]</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length &lt;= 100000</code></li>\n",
    "\t<li><code>-10^5 &lt;= nums[i], target &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pairs-with-sum-lcci](https://leetcode.cn/problems/pairs-with-sum-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pairs-with-sum-lcci](https://leetcode.cn/problems/pairs-with-sum-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        a,b=0,n-1\n",
    "        ret=[]\n",
    "        while 0<=a<n and 0<=b<n and a<b:\n",
    "            cur=nums[a]+nums[b]\n",
    "            if cur<target:\n",
    "                a+=1\n",
    "            elif cur>target:\n",
    "                b-=1\n",
    "            else:\n",
    "                ret.append([nums[a],nums[b]])\n",
    "                a+=1\n",
    "                b-=1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        l,r=0,n-1\n",
    "        while l<r:\n",
    "            if nums[l]+nums[r]==target:\n",
    "                ans.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "            elif nums[l]+nums[r]<target:\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "      nums = sorted(nums)\n",
    "      left = 0 \n",
    "      right= len(nums) - 1\n",
    "      results = []\n",
    "      while left < right:\n",
    "        if nums[left] + nums[right] == target:\n",
    "          results.append([nums[left],nums[right]])\n",
    "          left += 1\n",
    "          right -= 1\n",
    "        elif nums[left] + nums[right] < target:\n",
    "          left += 1\n",
    "        else:\n",
    "          right -= 1\n",
    "      return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums=sorted(nums)#sorted()函数，默认从小到大排序\n",
    "        low=0\n",
    "        high=len(nums)-1\n",
    "        result=[]\n",
    "        while low<high:\n",
    "            if nums[low]+nums[high]>target:\n",
    "                high-=1\n",
    "            elif nums[low]+nums[high]<target:\n",
    "                low+=1\n",
    "            else:\n",
    "                result.append([nums[low],nums[high]])\n",
    "                low+=1\n",
    "                high-=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums=sorted(nums)\n",
    "        low,high=0,len(nums)-1\n",
    "        results=[]\n",
    "        while low<high:\n",
    "            if nums[low]+nums[high]==target:\n",
    "                results.append([nums[low],nums[high]])\n",
    "                low+=1\n",
    "                high-=1\n",
    "            elif nums[low]+nums[high]<target:\n",
    "                low+=1\n",
    "            else:\n",
    "                high-=1\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        n=len(nums)\n",
    "        j=n-1\n",
    "        # if len(nums)%2==0:\n",
    "        #         k=len(nums)//2\n",
    "        # else:\n",
    "        #         k=len(nums)//2+1\n",
    "        for i in range(n):\n",
    "            # res=[]\n",
    "            # n=len(nums)\n",
    "            # j=n-1\n",
    "            while j>i:\n",
    "                if (target-nums[i]) == nums[j]:\n",
    "                    res.append([nums[i],nums[j]])\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                    break\n",
    "                elif (target-nums[i]) < nums[j]:\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                else:\n",
    "                    break\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        l,r=0,n-1\n",
    "        while l<r:\n",
    "            if nums[l]+nums[r]==target:\n",
    "                ans.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "            elif nums[l]+nums[r]<target:\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        # total_res=[]\n",
    "        res=[]\n",
    "        n=len(nums)\n",
    "        j=n-1\n",
    "        # if len(nums)%2==0:\n",
    "        #         k=len(nums)//2\n",
    "        # else:\n",
    "        #         k=len(nums)//2+1\n",
    "        for i in range(n):\n",
    "            # res=[]\n",
    "            # n=len(nums)\n",
    "            # j=n-1\n",
    "            while j>i:               \n",
    "                if (target-nums[i]) < nums[j]:\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                elif (target-nums[i]) == nums[j]:\n",
    "                    # res.extend([nums[i],nums[j]])\n",
    "                    # total_res.extend([res])\n",
    "                    res.append([nums[i],nums[j]])\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                    break\n",
    "                else:\n",
    "                    break\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums = sorted(nums)\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < target:\n",
    "                left += 1\n",
    "            elif nums[left] + nums[right] > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                ans.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        res = []\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] == target:\n",
    "                res.append([nums[left] , nums[right]])\n",
    "                left += 1\n",
    "                right -=1\n",
    "            elif nums[left] + nums[right] > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        res = []\n",
    "        while left < right:\n",
    "            temp = nums[left] + nums[right]\n",
    "            if temp < target:\n",
    "                left += 1\n",
    "            elif temp > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                res.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        l,r,res = 0,len(nums)-1,[]\n",
    "        while l<r:\n",
    "            tmp = nums[l]+nums[r]\n",
    "            if tmp<target:\n",
    "                l+=1\n",
    "            elif tmp>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                res.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        low, high = 0, len(nums) - 1\n",
    "        while low < high:\n",
    "            if nums[low] + nums[high] == target:\n",
    "                res.append([nums[low], nums[high]])\n",
    "                low += 1\n",
    "                high -= 1\n",
    "            elif nums[low] + nums[high] < target:\n",
    "                low += 1\n",
    "            else:\n",
    "                high -= 1\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        j=len(nums)-1\n",
    "        ans=[]\n",
    "        while i<j:\n",
    "            x=nums[i]\n",
    "            y=nums[j]\n",
    "            t = x+y\n",
    "            if t==target:\n",
    "                ans.append([x,y])\n",
    "                i+=1\n",
    "                j-=1\n",
    "            elif t>target:j-=1\n",
    "            else:i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        l,r,res = 0,len(nums)-1,[]\n",
    "        while l<r:\n",
    "            tmp = nums[l]+nums[r]\n",
    "            if tmp<target:\n",
    "                l+=1\n",
    "            elif tmp>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                res.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        l,r,res = 0,len(nums)-1,[]\n",
    "        while l<r:\n",
    "            tmp = nums[l]+nums[r]\n",
    "            if tmp<target:\n",
    "                l+=1\n",
    "            elif tmp>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                res.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] > target:\n",
    "                right -= 1\n",
    "            elif nums[left] + nums[right] == target:\n",
    "                res.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        ans = []\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < target:\n",
    "                left += 1\n",
    "            elif nums[left] + nums[right] > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                ans.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        left = 0\n",
    "        right = n-1\n",
    "\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] == target:\n",
    "                res.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            elif nums[left] + nums[right] < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        i, j = 0, len(nums) - 1 \n",
    "        res = []\n",
    "        while i < j:\n",
    "            tmp = nums[i] + nums[j]\n",
    "            if tmp == target:\n",
    "                res.append([nums[i], nums[j]])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            elif tmp < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        n=len(nums)\n",
    "        j=n-1\n",
    "        for i in range(n):\n",
    "            while j>i:\n",
    "                if (target-nums[i]) == nums[j]:\n",
    "                    res.append([nums[i],nums[j]])\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                    break\n",
    "                elif (target-nums[i]) < nums[j]:\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                else:\n",
    "                    break                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # two sum 的变形？\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        ret = []\n",
    "\n",
    "        while left < right:\n",
    "            if nums[left] >= target: break\n",
    "            curSum = nums[left] + nums[right]\n",
    "            if curSum > target:\n",
    "                right -= 1\n",
    "            elif curSum < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                ret.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        i,j = 0,n-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            elif nums[i] + nums[j] == target:\n",
    "                res.append([nums[i],nums[j]])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        n=len(nums)\n",
    "        j=n-1\n",
    "        if len(nums)%2==0:\n",
    "                k=len(nums)//2\n",
    "        else:\n",
    "                k=len(nums)//2+1\n",
    "        for i in range(k):\n",
    "            while j>i:\n",
    "                if (target-nums[i]) == nums[j]:\n",
    "                    res.append([nums[i],nums[j]])\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                    break\n",
    "                elif (target-nums[i]) < nums[j]:\n",
    "                    # nums.remove(nums[j])\n",
    "                    j=j-1\n",
    "                else:\n",
    "                    break                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        results = []\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] == target:\n",
    "                results.append([nums[i], nums[j]])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            elif nums[i] + nums[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        if len(nums) <2:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        res = []\n",
    "        while i < j:\n",
    "            tp = nums[i] + nums[j]\n",
    "            if tp == target:\n",
    "                res.append([nums[i],nums[j]])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            elif tp > target:\n",
    "                j -= 1\n",
    "            elif tp < target:\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        low, high = 0, len(nums) - 1\n",
    "        results = []\n",
    "        while low < high:\n",
    "            if nums[low] + nums[high] == target:\n",
    "                results.append([nums[low], nums[high]])\n",
    "                low += 1\n",
    "                high -= 1\n",
    "            elif nums[low] + nums[high] < target:\n",
    "                low += 1\n",
    "            else:\n",
    "                high -= 1\n",
    "        return  results\n",
    "\n",
    "\n",
    "# Python排序和双指针的解法\n",
    "# 作者：lvah\n",
    "# 链接：https://leetcode.cn/problems/pairs-with-sum-lcci/solutions/299256/pythonpai-xu-he-shuang-zhi-zhen-de-jie-fa-han-fen-/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<right:\n",
    "            if nums[left]+nums[right]==target:\n",
    "                aa=[nums[left],nums[right]]\n",
    "                \n",
    "                res.append(aa)\n",
    "                left+=1\n",
    "                right-=1\n",
    "            elif nums[left]+nums[right]<target:\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        if len(nums)==0:\n",
    "            return []\n",
    "        l,r = 0, len(nums)-1\n",
    "        nums.sort()\n",
    "        re = []\n",
    "        while l<r:\n",
    "            tmp = nums[l]+nums[r]\n",
    "            if tmp==target:\n",
    "                re.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "            elif tmp<target:\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        l,r=0,len(nums)-1\n",
    "        while l<r:\n",
    "            if nums[l]+nums[r]<target: l+=1\n",
    "            elif nums[l]+nums[r]>target: r-=1\n",
    "            else:\n",
    "                res.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        l, r = 0, len(nums)-1\n",
    "\n",
    "        res = []\n",
    "\n",
    "        while l < r:\n",
    "            temp = nums[l] + nums[r]\n",
    "            if temp == target:\n",
    "                res.append([nums[l], nums[r]])\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            elif temp < target: l += 1\n",
    "            else : r -= 1\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        l,r,res = 0,len(nums)-1,[]\n",
    "        while l<r:\n",
    "            tmp = nums[l]+nums[r]\n",
    "            if tmp<target:\n",
    "                l+=1\n",
    "            elif tmp>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                res.append([nums[l],nums[r]])\n",
    "                l+=1\n",
    "                r-=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        res = []\n",
    "        \n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] == target:\n",
    "                res.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            elif nums[left] + nums[right] < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()  # 对数组进行排序\n",
    "        left, right = 0, len(nums) - 1  # 初始化两个指针\n",
    "        pairs = []  # 用于存储结果的数组\n",
    "\n",
    "        while left < right:\n",
    "            curr_sum = nums[left] + nums[right]\n",
    "            \n",
    "            if curr_sum == target:\n",
    "                pairs.append([nums[left], nums[right]])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            elif curr_sum < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "        return pairs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        lo, hi = 0, len(nums) - 1\n",
    "        res = []\n",
    "        while lo < hi:\n",
    "            tmp = nums[lo] + nums[hi]\n",
    "            if tmp == target:\n",
    "                res.append([nums[lo], nums[hi]])\n",
    "                lo += 1\n",
    "                hi -= 1\n",
    "            elif tmp < target:\n",
    "                lo += 1\n",
    "            else:\n",
    "                hi -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        nums.sort()\n",
    "        while left<right:\n",
    "\n",
    "            if nums[left]+nums[right]==target:\n",
    "                res.append([nums[left],nums[right]])\n",
    "                left+=1\n",
    "                right-=1\n",
    "            elif nums[left]+nums[right]>target:\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return res\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef pairSums(self, nums, target):\n",
    "\t\tnums.sort()\n",
    "\t\tl = 0\n",
    "\t\tr = len(nums) - 1\n",
    "\t\tans = []\n",
    "\t\twhile l < r:\n",
    "\t\t\tif nums[l] + nums[r] == target:\n",
    "\t\t\t\tans.append([nums[l], nums[r]])\n",
    "\t\t\t\tl += 1\n",
    "\t\t\t\tr -= 1\n",
    "\t\t\telif nums[l] + nums[r] > target:\n",
    "\t\t\t\tr -= 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tl += 1\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        alist = []\n",
    "        while right-left>=1:\n",
    "            if nums[left]+nums[right]>target:\n",
    "                right-=1\n",
    "            elif nums[left]+nums[right]<target:\n",
    "                left+=1\n",
    "            else:\n",
    "                alist.append([nums[left],nums[right]])\n",
    "                left+=1\n",
    "                right-=1\n",
    "        return alist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        result=[]\n",
    "\n",
    "        while left<right:\n",
    "            two_sum=nums[left]+nums[right]\n",
    "            if two_sum==target:\n",
    "                result.append([nums[left],nums[right]])\n",
    "                left+=1\n",
    "                right-=1\n",
    "            elif two_sum<target:\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        mp = Counter(nums)\n",
    "        ans = defaultdict(int)\n",
    "        for k in mp:\n",
    "            if target - k in mp:\n",
    "                if k == target - k:\n",
    "                    ans[(k, k)] += mp[k]\n",
    "                else:\n",
    "                    mn, mx = min(k, target - k), max(k, target - k)\n",
    "                    ans[(mn, mx)] += min(mp[mn], mp[mx])\n",
    "        \n",
    "        t = []\n",
    "        for (x, y), cnt in ans.items():\n",
    "            for _ in range(cnt // 2):\n",
    "                t.append([x, y])\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        cnt = Counter(nums)\n",
    "        visited = set()\n",
    "        res = []\n",
    "        for k in cnt:\n",
    "            if k in visited:\n",
    "                continue\n",
    "            other = target-k\n",
    "            if other!=k:\n",
    "                if other in cnt:\n",
    "                    visited.add(other)\n",
    "                    for _ in range(min(cnt[k], cnt[other])):\n",
    "                        res.append([k, other])\n",
    "            else:\n",
    "                for _ in range(cnt[k]//2):\n",
    "                    res.append([k, k])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        if len(nums) <2:\n",
    "            return []\n",
    "        dic = {}\n",
    "        res = []\n",
    "        for num in nums:\n",
    "            if target - num in dic:\n",
    "                if dic[target - num] == 1:\n",
    "                    dic.pop(target - num)\n",
    "                else:\n",
    "                    dic[target - num] -= 1\n",
    "                res.append([num,target - num])\n",
    "            else:\n",
    "                if num in dic:\n",
    "                    dic[num] += 1\n",
    "                else :\n",
    "                    dic[num] = 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        visit = collections.defaultdict(int)\n",
    "        ans = list()\n",
    "        for num in nums:\n",
    "            if target - num in visit.keys():\n",
    "                ans.append([num, target - num])\n",
    "                if visit[target - num] == 1:\n",
    "                    visit.pop(target - num)\n",
    "                else:\n",
    "                    visit[target - num] -= 1\n",
    "            else:\n",
    "                visit[num] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "    r = {}\n",
    "    ret = []\n",
    "    for n in nums:\n",
    "      p = target - n\n",
    "      if r.get(p, 0) > 0:\n",
    "        ret.append([p, n])\n",
    "        r[p] -= 1\n",
    "      else:\n",
    "        r[n] = r.get(n, 0) + 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "       ans=[] \n",
    "       q=Counter() \n",
    "       for x  in nums:\n",
    "          if q[target-x]>0:\n",
    "             q[target-x]-=1\n",
    "             ans.append([x,target-x])\n",
    "          else:   \n",
    "             q[x]+=1\n",
    "       return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        cnt = {}\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if target - nums[i] in cnt and cnt[target-nums[i]]:\n",
    "                res.append([target-nums[i], nums[i]])\n",
    "                cnt[target-nums[i]] -= 1\n",
    "            else:\n",
    "                if nums[i] not in cnt:\n",
    "                    cnt[nums[i]] = 0\n",
    "                cnt[nums[i]] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        hashmap={}\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        for a in nums:\n",
    "            if a in hashmap:\n",
    "                hashmap[a]+=1\n",
    "            else:\n",
    "                hashmap[a]=1\n",
    "        for num in nums:\n",
    "            if hashmap[num]>=1:\n",
    "                hashmap[num]-=1\n",
    "                if target-num in hashmap and hashmap[target-num]>=1:\n",
    "                    res.append([num,target-num])\n",
    "                    hashmap[target-num]-=1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        mydict = {}\n",
    "        res = []\n",
    "\n",
    "        for n in nums:\n",
    "            if mydict.get(target-n, 0) > 0:\n",
    "                res.append([n, target-n])\n",
    "                mydict[target-n] -= 1 \n",
    "            else:\n",
    "                mydict[n] = mydict.get(n, 0) + 1 \n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        mydict = {}\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            if mydict.get(target-n, 0) > 0:\n",
    "                res.append([n, target-n])\n",
    "                mydict[target-n] -= 1\n",
    "            else:\n",
    "                mydict[n] = mydict.get(n, 0) + 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if x == target - x:\n",
    "                if cnt[x] > 1:\n",
    "                    cnt[x] -= 2\n",
    "                    ans.append([x, target-x])\n",
    "            else:\n",
    "                if cnt[x] > 0 and cnt[target - x] > 0:\n",
    "                    ans.append([x, target-x])\n",
    "                    cnt[x] -= 1\n",
    "                    cnt[target - x] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        mydict = {}\n",
    "        res = []\n",
    "\n",
    "        for n in nums:\n",
    "            if mydict.get(target-n, 0) > 0:\n",
    "                res.append([n, target-n])\n",
    "                mydict[target-n] -= 1 \n",
    "            else:\n",
    "                mydict[n] = mydict.get(n, 0) + 1 \n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if x == target - x:\n",
    "                if cnt[x] > 1:\n",
    "                    cnt[x] -= 2\n",
    "                    ans.append([x, target-x])\n",
    "            else:\n",
    "                if cnt[x] > 0 and cnt[target - x] > 0:\n",
    "                    ans.append([x, target-x])\n",
    "                    cnt[x] -= 1\n",
    "                    cnt[target - x] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        d=collections.defaultdict(int)\n",
    "        ans=[]\n",
    "        for num in nums:\n",
    "            if d.get(target-num,0)>0:\n",
    "                ans.append([num,target-num])\n",
    "                d[target-num]-=1\n",
    "            else:\n",
    "                d[num]+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        mydict = {}\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            if mydict.get(target-n, 0) > 0:\n",
    "                res.append([n, target-n])\n",
    "                mydict[target-n] -= 1\n",
    "            else:\n",
    "                mydict[n] = mydict.get(n, 0) + 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        freqs = {}\n",
    "        pairs = []\n",
    "        for num in nums:\n",
    "            other = target - num\n",
    "            if other in freqs:\n",
    "                pairs.append([other, num])\n",
    "                if freqs[other] == 1:\n",
    "                    freqs.pop(other)\n",
    "                else:\n",
    "                    freqs[other] -= 1\n",
    "            elif num not in freqs:\n",
    "                freqs[num] = 1\n",
    "            else:\n",
    "                freqs[num] += 1\n",
    "        return pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[5,6,5]\n",
    "11\n",
    "[5,6,5,6]\n",
    "11\n",
    "\n",
    "nums.length <= 100000\n",
    "-10^5 <= nums[i], target <= 10^5\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        cache = defaultdict(int)\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if target-x in cache and cache[target-x] > 0:\n",
    "                res.append([target-x, x])\n",
    "                cache[target-x] -= 1\n",
    "            else:\n",
    "                cache[x] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[5]\n",
    "1\n",
    "[5,6,5,6]\n",
    "11\n",
    "\n",
    "nums.length <= 100000\n",
    "-10^5 <= nums[i], target <= 10^5\n",
    "\n",
    "Array, Hash Table, Two Pointers, Counting, Sorting\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        cache = defaultdict(int)\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if target-x in cache and cache[target-x] > 0:\n",
    "                res.append([x, target-x])\n",
    "                if cache[target-x] > 0:\n",
    "                    cache[target-x] -= 1\n",
    "            else:\n",
    "                cache[x] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: list[int], target: int) -> list[list[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return res\n",
    "        dict = {}\n",
    "        for i in range(n):\n",
    "            v = dict.get(nums[i],0)\n",
    "            dict[nums[i]] = v+1\n",
    "        for i in range(n):\n",
    "            if dict.get(nums[i]) != 0 and dict.get(target-nums[i],0) != 0:\n",
    "                if nums[i] == target - nums[i] and dict.get(nums[i]) < 2:\n",
    "                    continue\n",
    "                res.append([nums[i], target-nums[i]])\n",
    "                dict[nums[i]] -= 1\n",
    "                dict[target-nums[i]] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        d = defaultdict(int)\n",
    "        ans = []\n",
    "        for num in nums:\n",
    "            d[num] += 1\n",
    "        for num in nums:\n",
    "            if d[num] == 0 or d.get(target - num) in [None,0] or num == target - num and d[num] < 2:\n",
    "                continue\n",
    "            ans.append([num,target-num])\n",
    "            d[target - num] -= 1\n",
    "            d[num] -= 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        n2idx = dict()\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ttarget = target - nums[i]\n",
    "            if ttarget in n2idx:\n",
    "                ans.append([ttarget, nums[i]])\n",
    "                n2idx[ttarget] -= 1\n",
    "                if n2idx[ttarget] == 0:\n",
    "                    n2idx.pop(ttarget)\n",
    "            else:\n",
    "                if nums[i] not in n2idx:\n",
    "                    n2idx[nums[i]] = 0\n",
    "                n2idx[nums[i]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        lookup = defaultdict(int)\n",
    "\n",
    "        for num in nums:\n",
    "            lookup[num] += 1\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        for num in nums:\n",
    "            if lookup[num] < 1:\n",
    "                continue\n",
    "            \n",
    "            lookup[num] -= 1 # 先减去num，防止只有一个值a，且num=rest=a，然后这个唯一的值a同时被当做num和rest使用了，重复使用多算了一个a值\n",
    "            rest = target-num\n",
    "            if rest in lookup and lookup[rest] > 0:\n",
    "                res.append([num, rest])\n",
    "                lookup[rest] -= 1\n",
    "            else:\n",
    "                lookup[num] += 1 # num没有用上，再加回来\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[5]\n",
    "1\n",
    "[5,6,5,6]\n",
    "11\n",
    "\n",
    "nums.length <= 100000\n",
    "-10^5 <= nums[i], target <= 10^5\n",
    "\n",
    "Array, Hash Table, Two Pointers, Counting, Sorting\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        cache = defaultdict(int)\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if target-x in cache and cache[target-x] > 0:\n",
    "                res.append([x, target-x])\n",
    "                cache[target-x] -= 1\n",
    "            else:\n",
    "                cache[x] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        cnts = Counter(nums)\n",
    "        ans = []\n",
    "        for x in sorted(set(nums)):\n",
    "            if x * 2 < target:\n",
    "                ans += [[x, target-x]] * min(cnts[target-x], cnts[x])\n",
    "            elif x * 2 == target:\n",
    "                ans += [[x, x]] * (cnts[x] // 2)\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        data = collections.defaultdict(list)\n",
    "        res = []\n",
    "        for num in nums:\n",
    "            diff = target - num\n",
    "            if num not in data:\n",
    "                data[diff].append(num)\n",
    "            else:\n",
    "                if len(data[num]) > 0:\n",
    "                    val = data[num].pop()\n",
    "                    res.append([val, num])\n",
    "                if len(data[num]) == 0:\n",
    "                    del data[num]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        table = defaultdict(int)\n",
    "        for num in nums:\n",
    "            remain = target - num\n",
    "            if table[remain] > 0:\n",
    "                table[remain] -= 1\n",
    "                ans.append([remain, num])\n",
    "            else:\n",
    "                table[num] += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        m = defaultdict(int)\n",
    "        res = []\n",
    "        for v in nums:\n",
    "            if m[target-v]:\n",
    "                res.append([target-v, v])\n",
    "                m[target-v] -= 1\n",
    "            else:\n",
    "                m[v] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        pre = defaultdict(int)\n",
    "        for num in nums:\n",
    "            if pre[target-num]:\n",
    "                ans.append([target-num, num])\n",
    "                pre[target-num] -= 1\n",
    "            else:\n",
    "                pre[num] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        pre = defaultdict(int)\n",
    "        for num in nums:\n",
    "            c = target - num \n",
    "            if pre[c]:\n",
    "                ans.append([c, num])\n",
    "                pre[c] -=1\n",
    "            else:\n",
    "                pre[num] += 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        cnt=defaultdict(int)\n",
    "        result=[]\n",
    "        for num in nums:\n",
    "            if cnt[target-num]>0:\n",
    "                cnt[target-num]-=1\n",
    "                result.append([target-num,num])\n",
    "            else:\n",
    "                cnt[num]+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        lookup = collections.defaultdict(int)\n",
    "        res = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if lookup[target - num] > 0:  \n",
    "                res.append([target - num, num])\n",
    "                lookup[target - num] -= 1\n",
    "                lookup[num] -= 1\n",
    "            lookup[num] += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        pre = defaultdict(int)\n",
    "        for num in nums:\n",
    "            if pre[target - num]:\n",
    "                ans.append([target - num, num])\n",
    "                pre[target - num] -= 1\n",
    "            else:\n",
    "                pre[num] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        # # 排序+双指针\n",
    "        # nums.sort()\n",
    "        # left, right = 0, len(nums) - 1\n",
    "        # res = []\n",
    "        \n",
    "        # while left < right:\n",
    "        #     if nums[left] + nums[right] == target:\n",
    "        #         res.append([nums[left], nums[right]])\n",
    "        #         left += 1\n",
    "        #         right -= 1\n",
    "        #     elif nums[left] + nums[right] < target:\n",
    "        #         left += 1\n",
    "        #     else:\n",
    "        #         right -= 1\n",
    "\n",
    "        # return res\n",
    "\n",
    "        # 哈希表\n",
    "        hashMap = collections.defaultdict(int)\n",
    "        res = []\n",
    "\n",
    "        for num in nums:\n",
    "            if hashMap[target - num]:\n",
    "                res.append([target - num, num])\n",
    "                hashMap[target - num] -= 1\n",
    "            else:\n",
    "                hashMap[num] += 1\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
